[Contrib] [Chalisti] [06]    Datensicherheit. Verschluesselung mit dem RSA-Code. Theoretisches.

Datensicherheit. Verschluesselung mit dem RSA-Code. Theoretisches. Das "public key"- System von R. L. Riverest, A. Shamir, L. M. Adleman (1978) (RSA- Code). (Anm. der Redaktion): Nachdem wir schon einen Beitrag zum Thema DES hatten, wollen wir Euch diesmal noch mal mit Mathematik aergern. Bei den Publik Key Verfahren handelt es sich um Verschluesselungsprogramme, wo es zwei Schluessel gibt: Einen zum Verschluesseln und einen zum Entschluesseln. Der zum verschluesseln kann allgemein bekannt sein. Er ist zum Entschluesseln nutzlos. Diese Ver- fahren haben den Vorteil, dass ein Nachteil von anderen Cryptoverfahren (z.B. DES) wegfaellt. Dort muss naemlich der Schluessel ausgetaucht werden, damit die Gegenstelle den Text wieder entschluesseln kann. Fuer die meisten "praktischen" Anwendungen (z.B> in der Wirtschaft) sind die Public Key Verfahren besser einsetzbar (Gute Informationen zu dem Thema kann mensch von der GMD, Berlinghoven zum Projekt TeleTrust erhalten). (Ende der Anmerkung) Die Benutzer eines oeffentlichen Kommunikativsystems wollen verschluesselte Botschaften austauschen. Es wird ein Alphabet mit N Zeichen benutzt. Die Zeichen werden durchnumeriert. Seinen b(0), b(1), ... b(N-1) die Buch- staben in diesem Alphabet. Diese Reihenfolge wird beibehalten. Man waehlt natuerliche Zahlen k und l mit k < l, fuer die N^k (N hoch k) und N^l (N hoch l) ca. 200 Dezimalstellen haben. Das Alphabet, die Reihenfolge der Zeichen, die Zahl N, und die Zahlen k und l werden veroeffentlicht. (1) Erzeugung des Codes Es sei A ein Benutzer dieses Systems. A waehlt zwei verschiedene Primzahlen p(A) und q(A) mit jeweils etwa 100 Dezimalstellen, die folgende Bedingung erfuellen : Es ist N^k < p(A) * q(A) < N^l Dann berechnet A die Zahlen m(A) = p(A) * q(A) und phi(A) = (p(A) -1) * (q(A) - 1) und waehlt eine Zahl e(A) zwischen 1 und phi(A)-1, die mit phi(A)-1 keinen gemeinsamen Teiler hat. Anschlieend berechnet A die Zahl d(A) fuer die gilt: Es gibt eine natuerliche Zahl k mit : d(A) * e(A) = 1 + phi(A) * k (Mathematisch: d(A) * e(A) ist kongruent zu 1 modulo phi(A)) (Fuer die Berechnung von d(A) gibt es schnelle Algorithmen. Eingabe dieser Algorithmen ist e(A) und phi(A). Die Geheimhaltung von phi(A) ist also dringend erforderlich, um die Sicherheit des Codes zu garantieren.) Die Zahlen m(A) und e(A) werden veroeffentlicht, die Zahlen p(A), q(A), d(A) und phi(A) muessen geheimgehalten werden. p(A), q(A) und phi(A) werden nicht mehr benoetigt. (2) Verschluesselung und Entschluesselung Der Benutzer B moechte an A eine verschluesselte Nachricht schicken. B teilt den Klartext in Bloecke aus k Zeichen und ersetzt jedes Zeichen durch sein "numerisches" quivalent (also jeweils b(i) durch i). So entstehen k-tupel aus Zahlen in {0, 1, ..., N-1}. Es sei (y(1), ..., y(k)) ein solches k-tupel. B berechnet X := y(1) * N^(k-1) + y(2) * N^(k-2) + ... + y(k-1) * N + y(k) und X1 := (X ^ e(A)) MOD m(a) Es gilt 0 < X < N^k-1 < N^l-1. B berechnet die z(1), ..., z(l) mit X1 = z(1) * N^(l-1) + z(2) * N^(l-2) + ... + z(l-1) * N + z(l). Das l-tupel (z(1), ..., z(l)) wird ueber das oeffentliche Kommunikations- system an A geschickt. A berechnet daraus wieder X1 = z(1) * N^(l-1) + ... + z(l), und dann X2 := (X1 ^ d(A)) mod m(A). Es gilt: X2 = X. Aus X berechnet A die Zahlen y(1), ..., y(k) mit X := y(1) * N^(k-1) + y(2) * N^(k-2) + ... + y(k-1) * N + y(k) und hat damit (y(1), ..., y(k)) zurueckgewonnen, und kann die Original- nachricht daraus zusammensetzen. Anmerkung: Die Gesamtnachricht setzt sich aus den Kodierungen aller k-tupel der Originalnachricht zusammen. Die Nachricht verlaengert sich beim kodieren also um das l/k-fache. Zum Kodieren ist die Kenntnis der Zahlen m(A), e(A), k, l, und N sowie die Kodierung der Zeichen im Alphabet notwendig. m(A) und e(A) haben jeweils ca. 200 Stellen und sind somit nur schweer zu merken, oder ueberall fuer jeweils alle Benutzer zu speichern. (3) Identifizierung von Nachrichten Jeder Teilnehmer erhaelt eine Signatur (g(1), ..., g(k)) aus Zeichen des Alphabets zugewiesen, die ihn eindeutig identifiziert (z. B. der Username), und die veroeffentlicht ist. B moechte mit seiner Botschaft an A einen Beweis dafuer mitschicken, da die Botschaft von ihm kommt. B berechnet mit seiner eigenen Signatur: s := g(1) * N^(k-1) + g(2) * N^(k-2) + ... + g(k-1) * N + g(k) und s1 := (s ^ d(B)) mod m(B) und ermittelt daraus die h(1),.. h(l) mit s1 = h(1) * N^(l-1) + h(2) * N^(l-2) + ... + h(l-1) * N + h(l) und schickt (h(1),..., h(l)) mit seiner Botschaft an A. A dechiffriert, wie in (2) beschrieben die eingegangenen l-tupel. Alle ergeben sinnvollen Klartext auer h(1),..., h(l). Hiermit berechnet er wieder s1 := h(1) * N^(l-1) + h(2) * N^(l-2) + ... + h(l-1) * N + h(l) und s := (s1 ^ e(B)) mod m(B) A schreibt s als: s = g(1) * N^(k-1) + g(2) * N^(k-2) + ... + g(k-1) * N + g(k) und hat damit (g(1), ..., g(k)) berechnet und vergleicht mit der veroeffentlichten Signatur im Telefonbuch. Anmerkung: Dieses Verfahren klappt nur dann, wenn man die Position der h(1), ..., h(l) in der verschluesselten Datei nicht im Vorraus ermitteln kann, und wenn B seine Identitaet bereits anderswo in der verschluesselten Datei andeutet. So bietet die hier beschriebene Methode eine Moeglichkeit, das Dokument zu "unterschreiben", so dass nicht jeder diese Unterschrift unter ein mit falschem Absender versehenen Brief schreiben kann. Wenn die Zahlen h(1), ..., h(l) jedoch einem dritten bekannt werden, so ist das Verfahren hinfaellig. Ausserdem muss B seine Identitaet anderswo im Dokument angeben, weil sonst der Empfaenger alle Moeglichkeiten fuer verschiedene Absender durchgehen muss. (4) Sicherheit Die Sicherheit des Systems beruht darauf, dass es (noch) keinen schnellen Algorithmus zur Faktorisierung grosser natuerlicher Zahlen gibt. Um eine an A gerichtete Nachricht zu entschluesseln benoetigt man d(A) und um d(A) zu berechnen benaetigt man die Faktorisierung von m(A) = p(A= * q(A). (5) Primzahlen Zur Herstellung von p(A) und q(A) und e(A) hat men einen Generator von Zufallszahlen zu verwenden (und einen schnellen Primzahltest) (6) Zum modernsten Stand - G. Brassard, Modern cryptology, 1988 - E. Kranakis, Primality and cryptography - N. Knoblitz, A course in number theory and cryptogrphy Quelle: Vorlesung ueber Lineare Algebra, Paderborn. Aus dem Zerberus. Anfragen bitte an ZENTRALE@BIONIC, da ich dem Namen des Autors verschlammt habe. -----------------------------------------------------------------------------

[Contrib] [Chalisti] [06]    Datensicherheit. Verschluesselung mit dem RSA-Code. Theoretisches.